#pragma once

#include <stddef.h>
#include <stdint.h>

/**
 * @brief AVL树节点结构
 */
struct AVLNode {
    AVLNode *parent = NULL; ///< 父节点指针
    AVLNode *left = NULL;   ///< 左子节点指针
    AVLNode *right = NULL;  ///< 右子节点指针
    uint32_t height = 0;    ///< 子树高度
    uint32_t cnt = 0;       ///< 子树大小
};

/**
 * @brief 初始化AVL树节点
 * @param node 要初始化的节点
 */
inline void avl_init(AVLNode *node) {
    node->left = node->right = node->parent = NULL;
    node->height = 1;
    node->cnt = 1;
}

/**
 * @brief 获取节点高度
 * @param node 节点指针
 * @return 节点高度，NULL节点返回0
 */
inline uint32_t avl_height(AVLNode *node) { 
    return node ? node->height : 0; 
}

/**
 * @brief 获取子树节点数量
 * @param node 节点指针
 * @return 子树节点数量，NULL节点返回0
 */
inline uint32_t avl_cnt(AVLNode *node) { 
    return node ? node->cnt : 0; 
}

/**
 * @brief 修复AVL树平衡性
 * @param node 需要修复的节点
 * @return 修复后的根节点
 */
AVLNode *avl_fix(AVLNode *node);

/**
 * @brief 删除AVL树节点
 * @param node 要删除的节点
 * @return 删除后的根节点
 */
AVLNode *avl_del(AVLNode *node);

/**
 * @brief 在AVL树中按偏移量查找节点
 * @param node 起始节点
 * @param offset 偏移量
 * @return 目标节点指针，未找到返回NULL
 */
AVLNode *avl_offset(AVLNode *node, int64_t offset); 